//
//  KthSmallest.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/7/2.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  378. 有序矩阵中第K小的元素    tag:堆   二分查找

import UIKit

/*
 378. 有序矩阵中第K小的元素
 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

  

 示例：

 matrix = [
    [ 1,  5,  9],
    [10, 11, 13],
    [12, 13, 15]
 ],
 k = 8,

 返回 13。
  

 提示：
 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。
 */

class KthSmallest: NSObject {
    
    func kthSmallest(_ matrix: [[Int]], _ k: Int) -> Int {
        return matrix.flatMap{$0}.sorted()[k-1]
    }
    //该暴力解法没有用到矩阵的任何性质  所以时间复杂度最高。
    /*
     关于map(映射)和flatMap
     https://www.jianshu.com/p/a1143add57d4
     
     let numbers = [1,2,3,4]
     let result = numbers.map { $0 + 2 }
     print(result)  // [3,4,5,6]
     
     
     
     result = numbers.flatMap { $0 + 2 }
     // [3,4,5,6]
     
     let numbersCompound = [[1,2,3],[4,5,6]];
     var res = numbersCompound.map { $0.map{ $0 + 2 } }
     // [[3, 4, 5], [6, 7, 8]]
     var flatRes = numbersCompound.flatMap { $0.map{ $0 + 2 } }
     // [3, 4, 5, 6, 7, 8]
     
     */
    
    
    
    //使用二分查找可最大限度利用矩阵的性质来提高效率
    /*
     https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/you-xu-ju-zhen-zhong-di-kxiao-de-yuan-su-by-leetco/
     */
}
